package tree;

import java.util.Stack;

/**
 * 题目：判断二叉树是否对称
 *
 * @Author Gavin
 * @date 2021.12.07 22:08
 */
public class tree_1 {
    /**
     *解题思路 两种：
     *  判断二叉树是否对称的条件就是 左子树是否等于右子数
     *
     *  第一种：递归
     *  第二中，借助一个stack
     */


    //递归的方式
    //Time:O(n) Space:O(n)
    public static boolean solution(TreeNode node){
        if(node==null)return true;
        return isEqual(node.left,node.right);
    }
    //第一种，递归判断两个节点是否相等
    private static boolean isEqual(TreeNode l,TreeNode r){
        if(l!=null&& r!=null){
            /**
             * 精华逻辑：
             *  对称的核心思想就是根节点的左子树左节点要和右子树的右节点相等
             *  并且最终的条件左右子树都是指向null
             */
            return l.val==r.val && (isEqual(l.left,r.right)) &&(isEqual(l.right,r.left));
        }else{
            return l==null && r==null;
        }
    }

    //第二种方式，借助一个stack
    //Time:O(n) Space:O(n)
    public static boolean solution2(TreeNode node){
        if(node==null)return true;
        Stack<TreeNode> s=new Stack<>();
        s.push(node.left);
        s.push(node.right);
        while (!s.isEmpty()){
            TreeNode t1=s.pop();
            TreeNode t2=s.pop();
            if(t1==null&&t2==null)continue;
            if(t1==null||t2==null)return false;
            if(t1.val!=t2.val)return false;
            s.push(t1.left);
            s.push(t2.right);
            s.push(t1.right);
            s.push(t2.left);
        }
        return true;
    }
}
